Computer networks continue to proliferate. As a result, data traffic among networks continues to increase, placing ever-increasing demands on the ability of network structures to transfer data between networks. Network data is usually transferred in data units referred to as "packets" (or datagrams) that are transmitted from a source machine and eventually received by a destination machine. While network data transfers may appear transparent to both the source machine and the destination machine, in actuality, the data packets are usually transferred between intermediate stages (referred to as "hops") by machines referred to as "routers." A router will receive a packet, examine destination information within the packet, and from this destination information, "forward" the packet to a "next" hop destination. In this manner, data is forwarded by one or more hops, and eventually arrives at the desired destination. The function of examining a destination address and determining next hop information is often referred to as "address matching."
Routing functions rely on an underlying standardization in the data packet format and transmission method (protocols). One of the most prevalent protocols is the internet protocol (IP). IP serves to route a given packet from a source to a destination. To accomplish this function an IP data packet will include an initial portion (header) that includes, among other information fields, a source address and a destination address. As noted above, it is the destination address that is utilized by a routing machine to transfer a data packet to its next hop or final destination. To accomplish the routing function, a router will typically include a "look-up" table that includes next hop information corresponding to particular destination addresses. The router examines the destination address of an incoming packet, looks up the next hop information, and uses the next hop information to forward the packet onward toward its destination.
Routing functions can be performed by general purpose processors that run a routing algorithm. Such an approach can result in limited throughput of data packets, be expensive in terms of component cost, and require considerable area to implement.
One way to address the need for faster routers is to fabricate an integrated circuit that is specialized to perform routing tasks. Such application specific integrated circuits (ASICs) are designed to perform particular routing functions such as address matching. Unfortunately, because ASICs are custom manufactured products, they can also be expensive to manufacture.
One type of device that is particularly suitable for router address matching functions, is a content addressable memory (CAM), also referred to as an "associative memory." A CAM includes a number of data storage locations, each of which can be accessed by a corresponding address. The order in which the data values are stored varies according to the type of CAM. As just one example, in a typical "binary" CAM, data can be stored in the first available "empty" location. Empty locations are distinguished from "full" (or valid) locations by a status bit associated with each storage location.
Valid locations can then be addressed according to the contents (data values) that they store. A data value is loaded into a comparand register. The value within the comparand register can then be compared to the data values within each valid location. In the event the value within the comparand register matches the value of a storage location, a match signal for the matching storage location will be generated. In the event there is more than one match, one match from the multiple matches will be selected according to predetermined priority criteria. The address corresponding to the match location can then be made available.
Referring now to FIG. 1, a prior art "binary" CAM cell is set forth in block schematic diagram and designated by the general reference character 100. The CAM cell 100 is shown to include a storage register 102 that stores a data value. The register 102 can be accessed (for a read or write operation) by activating a word line WL. In a write operation, data would be placed on a pair of complementary bit lines (B and /B) to force a logic value into the register 102. In a read operation, the register 102 would place a data value on the bit lines (B and /B). It is understood that the word line WL is common to a number of other CAM cells within the same row, and the bit line pair (BL and /BL) is common to a number of other CAM cells within the same column.
As shown in FIG. 1, the CAM cell 100 also includes a compare circuit 104 that receives the data values stored within the register 102 by way of data lines D and /D. In addition, the compare circuit 104 also receives complementary comparand values, by way of compare lines C and /C. The compare circuit 104 compares the data line values and comparand values, and in the event the values are the same, activates a match indication on match line M. In the particular prior art example of FIG. 1, the compare circuit 104 is an exclusive OR (XOR) circuit.
Referring now to FIG. 2, a prior art register that may be used as the register 102, is set forth in a block schematic diagram. The register is designated by the general reference character 200 and includes a pair of cross-coupled inverters I200 and I202. The inverters (I200 and I202) are "cross-coupled" in that the output of inverter I200 is coupled to the input of inverter I202, and vice versa. The outputs of the inverters (I200 and I202) provide the data values on lines D and /D. Thus, the node formed at the output of inverter I202 and the input of inverter I200 can be considered a data node. The inverters (I200 and I202) provide the storage function of the register 200, and are accessed by two n-channel pass transistors N200 and N202. Transistor N200 has a source-drain path coupled between bit line B and the input of inverter I200. Transistor N202 has a source-drain path coupled between bit line /B and the input of inverter I202. The gates of transistors N200 and N202 are commonly coupled to a word line WL.
FIG. 3 sets forth a prior art compare circuit 300 that may be used as the compare circuit 104 set forth in FIG. 1. The compare circuit is an XOR circuit that includes a first pair of n-channel transistors N300 and N302 arranged in series between a match node 302 and a ground voltage GND. The gate of transistor N300 receives a comparand value C. The gate of transistor N302 receives the complementary data value /D. The compare circuit 300 further includes a second pair of transistors N304 and N306 arranged in series between the match node 302 and the GND voltage. The gate of transistor N304 receives a complementary comparand value /C and the gate of transistor N306 receives a data value D. In the event the comparand values (C and /C) are different than the data values (D and /D, respectively), the match node 302 will be discharged to the GND voltage. However, in the event the comparand values (C and /C) are the same as the data values (D and /D), the match node 302 will remain at a precharged level, indicating a match.
As noted above, a binary CAM can provide a rapid look-up function for an IP address. However, this is only true when the look-up function is for IP addresses having the same number of bits. Unfortunately, IP addresses can have prefixes of variable length. For example, two addresses are set forth below. The prefix values that must be matched are shown as binary values (either 0 or 1). The remaining portion of the IP address that does not have to be matched is represented by a series of Xs. EQU 11110000 10XXXXXX XXXXXXXX XXXXXXXX (address 1) EQU 10101010 01010101 100XXXXX XXXXXXXX (address 2)
Thus, the first address requires a router to find a match with a 10-bit prefix, while the second address requires a match with a 19-bit prefix. For proper routing of data packets, a router must perform a longest prefix matching function.
A prior art way to address longest prefix matching is to utilize a "ternary" or "tertiary" CAM. In a ternary CAM, a data value is stored according to the length of its prefix. This is accomplished by providing a prefix (or mask) bit for each bit of data. An example of ternary CAM storage arrangement is illustrated by a table set forth in FIG. 4. The table of FIG. 4 describes a ternary CAM having eight locations, each of which can store a data word of four bits. Longest prefix matching is required, thus the ternary CAM is required to compare either all four bits, the first three bits, the first two bits or the first bit of the data words. To indicate which bits comprise a prefix, the ternary CAM includes prefix data corresponding to each storage locations. If reference is made to FIG. 4, it is shown that data location "0" stores the four-bit data value A3 A2 A1 A0. Corresponding to the data location 0 is the prefix value 1111. This prefix value indicates that all four bits are to be compared with a comparand value. In contrast, data location "5," which stores the four-bit data value F3 F2 F1 F0, has a prefix value of 1100. This prefix value indicates that the first two bits F3 and F2 are to be compared with a comparand value.
To better understand the operation of the preferred embodiment, and to emphasize the advantageous features of the preferred embodiment, a prior art ternary CAM cell will be described. The prior art ternary CAM cell is set forth in FIG. 5 and designated by the general reference character 500. The ternary CAM memory cell 500 includes some of the same circuit constituents as the binary CAM memory cell of FIG. 1. Namely, the ternary CAM memory cell 500 includes a data register 502 and a compare circuit 504. The data register 502 has the same general circuit structure as that set forth in FIG. 2. Similarly, the compare circuit 504 is an XOR circuit such as that set forth in FIG. 3. The data register 502 is coupled to a complementary bit line pair (B and /B) by a value word line (VWL). The compare circuit 504 receives the data value stored by the data register 502 and a comparand value (C and /C), and compares the two values to generate a pre-match value (PMATCH).
To accomplish the variable prefix matching function, the ternary CAM cell 500 further includes a mask register 506 and a mask circuit 508. The mask register 506 stores the match value that corresponds to the data value in the data register 502. For example, referring back to FIG. 4, the prefix value corresponding to the G3 value stored in location 6 is "1." The prefix value is the inverse of the mask value. Thus, if the data register 502 stores the G3 value, the mask register 506 would store a "0" value (i.e., the entire mask value for the data word at storage location 6 would be 0111, the inverse of the value shown in the table of FIG. 5).
In the prior art arrangement of FIG. 5, the mask register 506 has the same structure as the register set forth in FIG. 2. Accordingly, the mask value can be written into the mask register 506, by way of bit line pair (B and /B), by activating a corresponding mask word line 506. The value stored by the mask register 506 is supplied to the mask circuit 508. The mask circuit provides a match value MATCH depending upon the mask value MASK. In the event the MASK value is low (indicating that the stored data bit is a prefix bit, and so should be compared) the PMATCH value is provided as an output by the mask circuit 508 to generate the MATCH value. Conversely, when the MASK value is high (indicating that the stored data bit is not part of the prefix, and so should not be compared) the PMATCH value is prevented from being passed through the mask circuit 508.
FIG. 6 is a schematic diagram illustrating the mask circuit of the ternary CAM 500 of FIG. 5. The mask circuit 600 is shown to be a p-channel metal-oxide-semiconductor (MOS) transistor P600 having a source-drain path coupled between the PMATCH signal and the MATCH signal. The gate of transistor P600 is driven by the MASK (/PREFIX) signal.
While the ternary CAM 500 provides for parallel, variable prefix matching, if reference is made to FIGS. 2-6, it is shown that a single ternary CAM cell requires 17 transistors. This assumes that the inverters used within the registers 502 are complementary MOS (CMOS) inverters, and thus each include two transistors. In contrast, the binary CAM 100 includes 10 transistors. Accordingly, the implementation of a conventional ternary CAM 500 requires considerable area, as there can be thousands, or possibly millions of such cells within a CAM. Area in any semiconductor device is a premium commodity, as larger areas can translate directly into increased manufacturing costs. Thus, conventional ternary CAMs can be an expensive and complex solution to the longest prefix matching problem.
It would be desirable to arrive at some sort of approach to longest prefix matching that does not have the drawbacks associated with ternary CAMs. If such an approach could provide rapid variable prefix matching functions, without requiring excessive area to implement, an acute need in the network hardware field would be met.